package homework;

import java.util.*;

public class Test1 {
    public static void fun(int[] arr) {

        int cur = 0;
        int dest = -1;
        while (dest < arr.length - 1) {
            if (arr[cur] == 0) {
                dest++;
            }
            //注意：dest可能越界
            dest++;
            if (dest >= arr.length - 1) {
                break;
            }
            cur++;

        }
        if (dest == arr.length) {
            arr[--dest] = arr[cur];
            cur--;
            dest--;
        }
        while (cur >= 0) {
            if (arr[cur] == 0) {
                arr[dest] = 0;
                dest--;
            }
            arr[dest] = arr[cur];
            cur--;
            dest--;
        }
        System.out.println(Arrays.toString(arr));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        if (nums[0] > 0) {
            return list;
        }
        HashSet set = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                List<Integer> data = new ArrayList<>();
                if (nums[j] + nums[k] + nums[i] == 0) {
                    data.add(nums[i]);
                    data.add(nums[j]);
                    data.add(nums[k]);
                    if (set.contains(data)) {
                        set.add(data);
                        list.add(data);
                    }
                } else if (nums[j] + nums[k] + nums[i] <= 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return list;
    }

    public static int min(int target, int[] nums) {
        Arrays.sort(nums);

        int sum = 0;
        int ret = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += nums[i];
            ret++;
            if (sum >= target) {
                return ret;
            }
        }
        return 0;
    }

    public static List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList();
        char[] s = ss.toCharArray();
        int[] hash = new int[128];
        for (int i = 0; i < pp.length(); i++) {
            hash[pp.charAt(i)]++;
        }
        int[] tep = new int[128];
        int len = pp.length();
        for (int right = 0, left = 0; right < s.length; right++) {
            //进窗口
            tep[s[right]]++;
            len--;
            //进行判断
            if (hash[s[right]] == 0 && tep[s[right]] != 0) {
                System.out.println("true");
            }
            if (tep[s[right]] > hash[s[right]]) {
                System.out.println("true");
            }
            while ((hash[s[right]] != 0 && tep[s[right]] != 0) || tep[s[right]] > hash[s[right]]) {//出窗口
                tep[s[left]]--;
                left++;
                len++;
            }
            if (len == 0) {
                ret.add(left);
            }
        }
        return ret;
    }

    public static int takeAttendance(int[] records) {
        //暴力遍历
        //优化暴力成为二分
        int right = records.length - 1;
        int left = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = left + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    //    public static void main(String[] args) {
////        System.out.println(min(213, new int[]{12, 28, 83, 4, 25, 26, 25, 2, 25, 25, 25, 12}));
////        List<Integer> list = findAnagrams("abab", "ab");
////        list.forEach(x -> System.out.println(x));
//        System.out.println(takeAttendance(new int[]{0, 1, 2, 3, 5}));
//    }
//public static void main(String[] args) {
//    //1.进行数据输入处理
//    Scanner in = new Scanner(System.in);
//    int n = in.nextInt(),q = in.nextInt();
//    int arr[] = new int[n + 1];
//    for(int i = 1;i < n + 1;i++){
//        arr[i] = in.nextInt();
//    }
//    //2.对数据进行加工
//    int dp[] = new int[n + 1];
//    for(int i = 1; i < n+ 1;i++){
//        dp[i] = dp[i - 1] + arr[i];
//    }
//    //3.进行输出
//    while(q > 0){
//        int i = in.nextInt(), j = in.nextInt();
//        System.out.println(dp[j] - dp[i - 1]);
//        q--;
//    }
//}
    public static int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] ret = new int[mat.length][mat[0].length];
        int[][] dp = new int[mat.length + 1][mat[0].length + 1];

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }

        for (int i = 0; i < ret.length; i++) {
            int hMax = i + k >= mat.length ? mat.length - 1 : i + k;//行
            int hMin = i - k <= 0 ? 0 : i - k;
            for (int j = 0; j < ret[0].length; j++) {
                int lMax = j + k >= mat[0].length ? mat[0].length - 1 : j + k;//列
                int lMin = j - k <= 0 ? 0 : j - k;
//            ret[i][j] = dp[hMax][lMax] - dp[hMax][lMin - 1] - dp[hMin - 1][lMax] + dp[hMin-1][lMin-1];
                ret[i][j] = dp[hMax + 1][lMax + 1] - dp[hMax + 1][lMin - 1 + 1] - dp[hMin - 1 + 1][lMax + 1] + dp[hMin - 1 + 1][lMin - 1 + 1];
            }
        }
        for (int i = 0; i < ret[0].length; i++) {
            System.out.println(Arrays.toString(ret[i]));
        }


        return ret;
    }

    //[12,21,16],[27,45,33],[24,39,28]
//    public static void main(String[] args) {
//        int[][] arr = {
//                {1, 2, 3},
//                {4, 5, 6},
//                {7, 8, 9}
//        };
//        matrixBlockSum(arr,1);
//    }
    private static Boolean fun(String astr) {
        int a = 0;
        if (astr.length() > 26) {
            return false;
        }
        for (int i = 0; i < astr.length(); i++) {
            int x = astr.charAt(i) - 'a';
            if ((a >> x & 1) == 1) {
                return false;
            }
            a = a | (1 << x);
        }
        return true;
    }


    //    public static void main(String[] args) {
//        System.out.println(fun("leetcode"));
//    }
    public static int getSum(int a, int b) {
        // return a + b;嘿嘿，先过了
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((a >> i & 1) == 1 && (b >> i & 1) == 1) {

                if (ret >> (i + 1) == 1 && i + 2 < 32) {
                    ret = ret ^ 1 << (i + 2);
                    ret = ret & (~0 ^ 1 << i + 1);
                } else if (i + 1 < 32) ret = ret ^ 1 << (i + 1);

            } else if ((a >> i & 1) == 1 || (b >> i & 1) == 1) {

                if (ret >> i == 1 && i + 1 < 32) {
                    ret = ret ^ 1 << (i + 1);
                    ret = ret & (~0 ^ 1 << i);
                } else ret = ret ^ 1 << i;

            }
        }
        return ret;
    }

//    public static void main(String[] args) {
//        System.out.println(~0 ^ 1 <<8);
//        int sum = getSum(-12, -8);
//        System.out.println(sum);
//    }

    public static String modifyString(String s) {
//        char[] ss = s.toCharArray();
//        int len = ss.length;
//        int[] arr = new int[len];//记录？的位置
//        int index = -1;
//        for(int i = 0;i < len;i++){
//            int f = '?';
//            System.out.println(f);
//            if('?' == ss[i]){
//                index++;
//                arr[index] = i;
//            }
//        }
//        //进行替换
//        for(int n = 0;n <= index;n++){
//            int i = arr[n];
//            char left = 'A';
//            char right = 'A';
//            if(i - 1 >= 0){
//                left = ss[i - 1];
//            }
//            if(i + 1 < s.length()){
//                right = ss[i + 1];
//            }
//            for(int x = 0;x < 26;x++){
//                if(left == 'A' && right == 'A'){
//                    ss[i] = 'a';
//                    break;
//                }else if(left != 'A' && right != 'A'){
//                    if(left != 'a' + x && right != 'a' + x){
//                        int tep = 'a' + x;
//                        ss[i] = (char)tep;
//                        break;
//                    }
//                }else if(left != 'A'){
//                    if(left != 'a' + x){
//                        int tep = 'a' + x;
//                        ss[i] = (char)tep;
//                        break;
//                    }
//                }else{
//                    if(right != 'a' + x){
//                        int tep = 'a' + x;
//                        ss[i] = (char)tep;
//                        break;
//                    }
//                }
//            }
//        }
//        return String.valueOf(ss);
        char[] ss = s.toCharArray();
        int len = ss.length;
        for (int i = 0; i < len; i++) {
            if (ss[i] == '?') {//说明i位置是？,所以进行替换
                for (int x = 'a'; x <= 'z'; x++) {
                    if ((i == 0 || ss[i - 1] != x) && (i == len - 1 || ss[i + 1] != x)) {
                        ss[i] = (char) x;
                        break;
                    }
                }
            }
        }
        return String.valueOf(ss);
    }

//    public static void main(String[] args) {
//        String s = modifyString("??yw?ipkj?");
//        System.out.println(s.toString());
//    }

    public static String convert(String s, int numRows) {
        int n = s.length();
        char[][] arr = new char[numRows][n];
        int l = 0;
        int i = 0;
        while (i < n) {
            for (int h = 0; h < numRows && i < n; h++) {
                arr[h][l] = s.charAt(i++);

            }
            l++;
            for (int h = numRows - 2; h > 0 && i < n; h--) {
                arr[h][l] = s.charAt(i++);
                l++;
            }
        }
        for (int j = 0; j < numRows; j++) {
            System.out.println(Arrays.toString(arr[j]));
        }
        String ret = "";
        for (int j = 0; j < arr.length; j++) {
            ret += String.valueOf(arr[j]).replace(" ", " ");
        }
        return ret;
    }

    public static String convert1(String ss, int numRows) {
        if (numRows == 1) {
            return ss;
        }
        String ret = "";
        int d = 2 * numRows - 2;
        char[] s = ss.toCharArray();
        int n = s.length;
        for (int h = 0; h < numRows; h++) {
            int k = 1;
            for (int i = h; i < n; i = i + d) {
                if (h == 0 || h == numRows - 1) {
                    ret += s[i];
                } else {
                    ret += s[i];
                    if (k * d - i < n) {
                        ret += s[k * d - i];
                    }
                }
                k = k + 2;
            }
        }
        return ret;
    }

    //    public static void main(String[] args) {
//        String paypalishiring = convert1("PAYPALISHIRING", 3);
//        System.out.println(paypalishiring);
//        StringBuffer buffer = new StringBuffer();
//
//    }
    public static String countAndSay(int n) {
        String ret = "1";
        while (n > 1) {
            StringBuffer tep = new StringBuffer();
            int sum = 1;
            for (int slow = 0, fast = 1; fast <= ret.length(); fast++) {
                if (fast == ret.length() || ret.charAt(slow) != ret.charAt(fast)) {
                    tep.append(sum + "" + ret.charAt(slow));
                    slow = fast;
                    sum = 1;
                } else {
                    sum++;
                }
            }
            ret = tep.toString();
            n--;
        }
        return ret;
    }

    //    public static void main(String[] args) {
//        String s = countAndSay(4);
//        System.out.println(s);
//    }
    public static int minNumberOfFrogs(String croakOfFrogs) {
        int maxRet = 0;
        int n = croakOfFrogs.length();
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('c', 0);
        map.put('r', 0);
        map.put('o', 0);
        map.put('a', 0);
        map.put('k', 0);
        int max = 0;
        for (int i = 0, slow = 0; i < n; slow++) {
            while (i < n && croakOfFrogs.charAt(i) != 'k') {
                if (croakOfFrogs.charAt(i) == 'c') {
                    max++;
                }
                map.put(croakOfFrogs.charAt(i), map.get(croakOfFrogs.charAt(i)) + 1);
                int a = map.get('a'), k = map.get('k'), c = map.get('c'), o = map.get('o'), r = map.get('r');
                if (!(c >= r && r >= o && o >= a && a >= k)) {
                    return -1;
                }
                i++;
            }
            if (i < n) {
                map.put(croakOfFrogs.charAt(i), map.get(croakOfFrogs.charAt(i)) + 1);
                if (map.get('a') < map.get('k')) {
                    return -1;
                }
            }
            i++;
            if (max > maxRet) {
                maxRet = max;
            }
            max--;
        }
        int a = map.get('a'), k = map.get('k');
        if (a != k) {
            return -1;
        }
        return maxRet;
    }

//    public static void main(String[] args) {
//        int i = minNumberOfFrogs("ccccccccccrrccccccrcccccccccccrcccccccccrcccccccccccrcccccrcccrrcccccccccccccrocrrcccccccccrccrocccccrccccrrcccccccrrrcrrcrccrcoccroccrccccccccorocrocccrrrrcrccrcrcrcrccrcroccccrccccroorcacrkcccrrroacccrrrraocccrrcrrccorooccrocacckcrcrrrrrrkrrccrcoacrcorcrooccacorcrccccoocroacroraoaarcoorrcrcccccocrrcoccarrorccccrcraoocrrrcoaoroccooccororrrccrcrocrrcorooocorarccoccocrrrocaccrooaaarrcrarooaarrarrororrcrcckracaccorarorocacrrarorrraoacrcokcarcoccoorcrrkaocorcrcrcrooorrcrroorkkaaarkraroraraarooccrkcrcraocooaoocraoorrrccoaraocoorrcokrararrkaakaooroorcororcaorckrrooooakcarokokcoarcccroaakkrrororacrkraooacrkaraoacaraorrorrakaokrokraccaockrookrokoororoooorroaoaokccraoraraokakrookkroakkaookkooraaocakrkokoraoarrakakkakaroaaocakkarkoocokokkrcorkkoorrkraoorkokkarkakokkkracocoaaaaakaraaooraokarrakkorokkoakokakakkcracarcaoaaoaoorcaakkraooaoakkrrroaoaoaarkkarkarkrooaookkroaaarkooakarakkooaokkoorkroaaaokoarkorraoraorcokokaakkaakrkaaokaaaroarkokokkokkkoakaaookkcakkrakooaooroaaaaooaooorkakrkkakkkkaokkooaakorkaroaorkkokaakaaaaaocrrkakrooaaroroakrakrkrakaoaaakokkaaoakrkkoakocaookkakooorkakoaaaaakkokakkorakaaaaoaarkokorkakokakckckookkraooaakokrrakkrkookkaaoakaaaokkaokkaaoakarkakaakkakorkaakkakkkakaaoaakkkaoaokkkakkkoaroookakaoka" +
//                "akkkkkkakoaooakcokkkrrokkkkaoakckakokkocaokaakakaaaka" +
//                "kaakakkkkrakoaokkaakkkkkokkkkkkkkrkakkokkroaakkakaoakk" +
//                "oakkkkkkakakakkkaakkkkakkkrkoak");
//        System.out.println(i);
//    }


    public static int findKthLargest(int[] nums, int k) {//需要创建小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            priorityQueue.add(nums[i]);
        }
        for (int i = k; i < n; i++) {
            if (priorityQueue.peek() < nums[i]) {
                priorityQueue.poll();
                priorityQueue.add(nums[i]);
            }
        }

        return priorityQueue.peek();
    }

//    public static void main(String[] args) {
//        int kthLargest = findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2);
//        System.out.println(kthLargest);
//    }

    public static int[] inventoryManagement(int[] nums, int k) {
//        int ret = qsort(nums,0,nums.length-1,k);
        qsort(nums, 0, nums.length - 1, k);
        int[] r = new int[k];
        if (k == 0) return r;
        for (int i = 0; i < k; i++) {
            r[i] = nums[i];
        }
        System.out.println(Arrays.toString(nums));

        return r;
    }

    public static int qsort(int[] nums, int left, int right, int k) {
        if (left >= right) {
            return right;
        }
        int standard = nums[left + (right - left) / 2];
        int i = left;
        int l = left - 1, r = right + 1;
        while (i < r) {
            if (nums[i] > standard) swap(nums, i, --r);
            else if (nums[i] == standard) i++;
            else swap(nums, i++, ++l);
        }
//        nums[0 -> l] < standard , nums[l+1 -> r-1] = standard , nums[r -> ---] > standard
        if (l > k) return qsort(nums, left, l, k);
        else if (k < r) return k;
        else return qsort(nums, r, right, k);
//        qsort(nums,left,l,k);
//        qsort(nums,r,right,k);
    }

    public static void swap(int[] nums, int x, int y) {
        int tep = nums[x];
        nums[x] = nums[y];
        nums[y] = tep;
    }

    //归并排序
    public static void merger(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        //进行递归
        int mid = left + (right - left) / 2;
        merger(nums, left, mid);
        merger(nums, mid + 1, right);
        //合并排序
        int r = mid + 1;
        while (left <= right && right >= r) {
            //进行插入排序
            if (nums[left] <= nums[r]) {
                left++;
            } else {
                int tep = nums[r];
                for (int index = r; index > left; index--) {
                    nums[index] = nums[index - 1];
                }
                nums[left] = tep;
                r++;
            }
        }
    }
//    public static void main(String[] args) {
//        int[] nums = new int[]{5,2,3,1};
//        merger(nums,0,nums.length-1);
//        System.out.println(Arrays.toString(nums));
//        List<int[]> nums1 = List.of(nums);
//    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public static void reorderList(ListNode head) {
        int size = 0;
        //1.相反顺序链表
        ListNode daeh = new ListNode();
        for (ListNode tep = head, cur = daeh; tep != null; tep = tep.next) {
            ListNode curN = cur.next;
            cur.next = new ListNode(tep.val);
            cur.next.next = curN;
            size++;
        }
        // head.next = daeh.next;
        daeh = daeh.next;
        ListNode ret = new ListNode();
        ListNode cur = ret;
        for (int len = size / 2; len > 0; len--) {
            cur.next = head;
            head = head.next;
            cur.next.next = daeh;
            cur = cur.next.next;
            daeh = daeh.next;
        }
        if (size % 2 == 1) {
            cur.next = head;
            cur = cur.next;
        }
        cur.next = null;
        ret = ret.next;
    }

//    public static void main(String[] args) {
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(2);
//        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        reorderList(l1);
//        ArrayList<ArrayList<String>> arrayLists = new ArrayList<>();
//        LinkedList<LinkedList<String>> list = new LinkedList<>();
//    }

    public static String addBinary(String a, String b) {
        String retS = "";
        int na = a.length() - 1;
        int nb = b.length() - 1;
        int c = 0;
        while (na >= 0 && nb >= 0) {
            int aData = a.charAt(na) - 48;
            int bData = b.charAt(nb) - 48;
            retS = (aData + bData + c) % 2 + retS;
            if (aData + bData + c != 3) {
                if (aData + c == 2 || bData + c == 2) {
                    c--;
                }
                if (aData + bData == 2) {
                    c++;
                }
            }
            na--;
            nb--;
        }
        while (na >= 0) {
            int aData = a.charAt(na) - 48;
            retS = (aData + c) % 2 + retS;
            if (aData + c != 2) {
                c = 0;
            }
            na--;
        }
        while (nb >= 0) {
            int bData = b.charAt(nb) - 48;
            retS = (bData + c) % 2 + retS;
            if (bData + c != 2) {
                c = 0;
            }
            nb--;
        }
        if (c == 1) {
            retS = 1 + retS;
        }
        return retS;
    }

//    public static void main(String[] args) {//,"cbbd"
//        System.out.println(calculate("1*2-3/4+5*6-7*8+9/10"));
//    }
    public static String fun(String c,int index){
        int n = c.length();
        if(c.charAt(index) >= '0' && c.charAt(index) <= '9'){
            int begin = index++;
            while(index < n && c.charAt(index) >= '0' && c.charAt(index) <= '9'){
                index++;
            }
            return c.substring(begin,index);
        }
        return c.charAt(index) + "";
    }
    public static int calculate(String s) {
        s =s.replaceAll(" ","");
        int n = s.length();
        Stack<String> stack = new Stack();
        for(int i = 0;i < n;i++){
            if(s.charAt(i) == '*'){
                int data1 = Integer.parseInt(stack.pop());
                String xxx = fun(s,i+1);
                int data2 = Integer.parseInt(xxx);
                stack.push((data1 * data2) + "");
                i+= xxx.length();
            }else if(s.charAt(i) == '/'){
                int data1 = Integer.parseInt(stack.pop());
                String xxx = fun(s,i+1);
                int data2 = Integer.parseInt(xxx);
                stack.push((data1 / data2) + "");
                i+= xxx.length();
            }else{
                String tep = fun(s,i);
                i += tep.length() - 1;
                stack.push(tep);
            }
        }

        Stack<String> teps = new Stack();
        while(!stack.empty()){
            teps.push(stack.pop());
        }
        // int data = 0;
        //     if(!teps.empty())
        int ret = Integer.parseInt(teps.pop());
        while(!teps.empty()){
            char c = teps.pop().charAt(0);
            int data = Integer.parseInt(teps.pop());
            if(c == '+') ret += data;
            else if (c == '-') ret -= data;
        }

        return ret;
    }



    public static String longestPalindrome(String s) {
        String ret = "";
        int n = s.length();
        for(int i = 1;i < n;i++){
            int left = i - 1;
            int right = i + 1;
            if(left >= 0 && right < n && s.charAt(right) == s.charAt(left)){
                while(left >= 0 && right < n){
                    if(s.charAt(right) != s.charAt(left)){
                        break;
                    }
                    right++;left--;
                }
            }else if(left >= 0 && right < n && s.charAt(i) == s.charAt(left)){
                left--;
                while(left >= 0 && right < n){
                    if(s.charAt(right) != s.charAt(left)){
                        break;
                    }
                    right++;left--;
                }
            }else{
                left = i;
                right = i;
            }
            if(left < 0) left = 0;
            if(ret.length() < right - left - 1){
                ret = s.substring(++left,right);
            }
        }
        return ret;
    }

//    public static void main(String[] args) {
//        char[][] c = new char[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
//        System.out.println(numIslands(c));
//    }


//    public static int[] a = new int[]{0,0,-1,1};
//    public static int[] b = new int[]{1,-1,0,0};

    public static int[] check(char[][] c){
        int m = c.length;
        int n = c[0].length;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(c[i][j] == '1') return new int[]{i,j};
            }
        }
        return new int[]{-1,-1};
    }

    public static int numIslands(char[][] grid) {
        int ret = 0;
        int m = grid.length;
        int n = grid[0].length;
        while(true){
            int[] tep = check(grid);
            int x = tep[0],y = tep[1];
            if(x == -1){
                break;
            }
            ret++;

            Queue<int[]> qu = new LinkedList<>();
            qu.add(new int[]{x,y});
            grid[x][y] = '0';
            while(!qu.isEmpty()){
                int[] dd = qu.poll();
                int xx = dd[0],yy = dd[1];
                for(int i = 0;i < 4;i++){
                    if(xx+a[i] >= 0 && xx+a[i] < m && yy+b[i] >= 0 && yy+b[i] < n && grid[xx + a[i]][yy + b[i]] == '1'){
                        qu.add(new int[]{xx + a[i],yy + b[i]});
                        grid[xx + a[i]][yy + b[i]] = '0';
                    }
                }
            }
        }
        return ret;
    }





    public static int[] a = new int[]{0,0,-1,1};
    public static int[] b = new int[]{1,-1,0,0};
    public static boolean[][] fase;
    public static int m; public static int n;

    public static int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        fase = new boolean[m][n];
        int retMax = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid[i][j] == 1 && !fase[i][j]){
                    int tep = fun(grid,i,j);
                    if(retMax < tep) retMax = tep;
                }
            }
        }
        return retMax;
    }

    public static int fun(int[][] g,int i,int j){
        int ret = 0;
        Queue<int[]> qu = new LinkedList<>();
        qu.add(new int[]{i,j});
        fase[i][j] = true;
        while(!qu.isEmpty()){
            int[] tep = qu.poll();
            ret++;
            for(int in = 0;i < 4;i++){
                int x = tep[0] + a[in];
                int y = tep[1] + b[in];
                if(x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1 && !fase[x][y]){
                    qu.add(new int[]{x,y});
                    fase[i][j] = true;
                }
            }
        }
        return ret;
    }

//    public static void main(String[] args) {
//        System.out.println(maxAreaOfIsland(new int[][]{
//                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
//                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
//                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}}));
//    }





    public static  List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(String s : words){
            int value = (map.containsKey(s)  ? map.get(s) : 0) + 1;
            map.put(s, value);
        } //(o1,o2) -> o2.getValue() - o1.getValue()
        PriorityQueue<Map.Entry<String,Integer>> qu = new PriorityQueue<>((o1,o2) -> o2.getValue() - o1.getValue());
        for(Map.Entry<String,Integer> tep : map.entrySet()){
            qu.add(tep);
            if(qu.size() > k){
                qu.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while(!qu.isEmpty()){
            ret.add(qu.poll().getKey());
        }
        return ret;
    }


    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
    }


}
//    public static void main(String[] args) {
//        String s = addBinary("11", "1");
//        StringBuilder stringBuilder = new StringBuilder();
//        stringBuilder.d
//        }
//    }
//}public String fun(int i,String ss){
//        StringBuilder ret = new StringBuilder();
//        while(i < ss.length() && ss.charAt(i) >= '0' && ss.charAt(i) <= '9'){
//        ret.append(ss.charAt(i++));
//        }
//        return ret.toString();
//        }
//public int calculate(String s) {
//        int ret = 0;
//        int n = s.length();
//        for(int i = 0;i < n;){
//        String data1 = fun(i,s);
//        int x1 = data1.length() > 0 ? Integer.parseInt(data1) : 0;
//        i += data1.length();
//        char c = s.charAt(i++);
//        String data2 = fun(i,s);
//        int x2 = data2.length() > 0 ? Integer.parseInt(data2) : 0;
//        i += data2.length();
//        switch(c){
//        case '+' : ret +=  x1 + x2;break;
//        case '-' : ret +=  x1 - x2;break;
//        case '*' : ret +=  x1 * x2;break;
//        case '/' : ret +=  x1 / x2;break;
//        }
//        }
//        return ret;




